Crossbars are well known in the art, dating back to the days of early telephony switches. Their aim was to connect between a caller and a receiver in electromechanical telephony exchanges. In the digital era, crossbar switches are high speed switching devices commonly used for transferring packet switched data in communications systems, allowing the matching of sources with desired destinations. Crossbars establish concurrent connections between a plurality of inputs and a plurality of outputs. A common problem with crossbars occurs when multiple packets arrive simultaneously at the same input, or if multiple packets are destined to the same output. In such cases the passage of cells or packets through the switches has to be efficiently scheduled. Therefore, packets waiting to be scheduled (i.e., to be sent to their intended destination) are kept in a queue or a buffer.
A key factor in the design of a crossbar scheduler is to achieve maximum throughput. Additionally, the scheduler has to ensure fairness, or in other words to provide for each input-output connection its fair share of bandwidth. An efficient scheduler should also avoid cases of starvation (i.e., each input-output connection should not wait longer than a predefined amount of time to be connected).
One type of scheduling techniques for crossbars is based upon matching. Schedulers which use the abovementioned matching technique, make matches between the input adapters of a switch, herein referred to as “ingress”, and the output adapters of a switch, herein referred to as “egress”. The scheduler matches ingresses that arbitrate for service with one or more egresses. One of the ways to match ingresses to egresses is the iterative serial-line Internet protocol hereinafter, referred to as the “ISLIP” algorithm. The ISLIP algorithm performs ingress to egress matching in three steps: (a) the request step; (b) the grant step; and (c) the accept step. In the request step, the ingresses post requests to all egresses to which they desire access. In the grant step, each egress selects one such request and asserts a response signal stating the selected request. In the accept step, if an ingress receives a grant from only one egress, the ingress simply accepts it. If, on the other hand, the ingress receives more than one grant, it selects only one of the grants and accepts it. The selections that are made in both the grant and accept steps are made by means of a selection algorithm such as random, round robin, weighted round robin, or any other priority based selection algorithm.
Reference is now made to FIG. 1, where an example for using the ISLIP algorithm is shown. FIG. 1A shows the request step, where ingress “1” requests for egresses “1” and “2”, ingress “3” requests for egresses “2” and “4”, and ingress “4” requests for egress “4”. FIG. 1B shows a possible grant step where each egress selects an input among those that requested it. In the example egress “1” selects ingress “1”, and both egresses “2” and “4” select ingress “3”. FIG. 1C shows the accept step where each ingress selects one of the granted egresses. In the example, ingress “1” accepts egress “1”, and ingress “2” accepts egress “3”, ingress “4” did not receive a match in this round.
Typically in crossbar systems each egress is connected to a plurality of ports, each of which ports has the capability to provide egress services to the different ingresses (i.e., if there is one egress, and it is connected to 4 ports, a requesting ingress can post 4 different requests, one to each of said ports). In systems that have a large number of ports and/or egresses, the number of requests posted by the ingresses can be very large (even larger than 256 requests, which is the maximum number of requests a crossbar in accordance with the prior art can efficiently handle). The upper bound of the number of requests posted is equal to P*E where “E” is the number of egresses and “P” is the number of ports connected to each of the egresses. For example if “E” equals 16 and “P” equals 64 then the upper bound of the number of requests is 1024. One known technique to deal with a large number of requests is by using the time slot algorithm. The time slot algorithm assigns each port a predetermine time farm, in which the designated port is opened for packets transmitting. However, the time slot algorithm does not schedule connections according to different priorities of the ports, as performed in accordance with the present invention.
The prior art provides no crossbar switch capable of scheduling connections in accordance with prioritiesed connections (i.e., where each connection has a different priority grade), nor for that matter can it efficiently scheduling a number of requests higher than 256.